package sorted;

/**
 * 功能描述:排序示例
 * 2025/04/19
 *
 * @author ZhangYi
 */
public class SortedExample {

	public static void main(String[] args) {
		int[] arr = new int[]{2, 22, 31, 231, 23, 3, 41, 23, 1, 2, 3, 4};
		printArray(arr);
		// 选择排序
//		selectSort(arr);
		// 冒泡排序
//		bubbleSort(arr);
		// 插入排序
//		insertSort(arr);
		printArray(arr);
	}


	/**
	 * 插入排序
	 *
	 * @param arr arr
	 * @author ZhangYi
	 */
	public static void insertSort(int[] arr) {
		//exit condition
		if (arr == null || arr.length < 2) {
			return;
		}

		int N = arr.length;
		for (int start = 0; start < N; start++) {
			int newValueIndex = start;
			while (newValueIndex - 1 >= 0 && arr[newValueIndex] < arr[newValueIndex - 1]) {
				swapArrayValue(arr, newValueIndex, newValueIndex - 1);
				newValueIndex--;
			}
		}
	}

	/**
	 * 冒泡排序
	 *
	 * @param arr arr
	 * @author ZhangYi
	 */
	public static void bubbleSort(int[] arr) {
		// exit condition
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1
		// 0 ~ N-2
		// 0 ~ N-3
		int N = arr.length;
		for (int start = N -1 ; start >=0; start--){
			for (int end=0;end < start;end++){
				if (arr[start] < arr[end]){
					swapArrayValue(arr,start,end);
				}
			}
		}

	}
	/**
	 * 选择排序 :
	 * 	认定 第一个元素的最小的,然后 0~N-1 寻找最小的,然后交换到0位置,
	 * 	认定 第二个元素的最小的,然后 1~N-1 寻找最小的,然后交换到1位置,
	 * 	......
	 *
	 * @param arr arr
	 * @author ZhangYi
	 */
	public static void selectSort(int[] arr) {
		// exit condition
		if (arr == null || arr.length < 2) {
			return;
		}
		int N = arr.length;
		for (int start = 0; start < N; start++) {
			int minValueIndex = start;
			for (int end = start + 1; end < N; end++) {
				minValueIndex = arr[end] < arr[minValueIndex] ? end : minValueIndex;
			}
			swapArrayValue(arr, start, minValueIndex);
		}
	}

	/**
	 * 交换数组值
	 *
	 * @param arr arr
	 * @param i   我
	 * @param j   j
	 * @author ZhangYi
	 */
	private static void swapArrayValue(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	/**
	 * 打印数组
	 *
	 * @param arr arr
	 * @author ZhangYi
	 */
	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + ",");
		}
		System.out.println();
	}
}
